/**
 * 合并区间
 *
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * 示例 2：
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * 提示：
 * 1 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 104
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 这里我们将数组按照第一个数排好序, 然后再比较相邻的两个数组第一个是后面一个数, 第二个是
 * 后面两个数
 * 时间复杂度 : O(n * log n)
 * 空间复杂度 : O(n)
 */

public class Main {

    // ****************************
    // 用 stack 来写

    public int[][] merge(int[][] nums) {

        // 通过比较器重新排序, 用 lambda 表达式写
        Arrays.sort(nums, (a, b) -> a[0] - b[0]);

        // 定义出 stack
        Stack<int[]> stack = new Stack<>();

        // 数组的长度
        int n = nums.length;

        // 遍历
        for (int i = 0; i < n; i++) {

            // 定义数组的两个数
            int c = nums[i][0];
            int d = nums[i][1];

            if (stack.isEmpty()) {
                // 要是 stack 为空直接入 stack
                stack.push(new int[]{c, d});
            } else {

                // 取出 stack 的 末尾的数
                int a = stack.peek()[0];
                int b = stack.peek()[1];

                // 先于 c 进行比较
                if (b == c) {

                    stack.pop();
                    stack.push(new int[]{a, d});

                } else if (b < c) {

                    stack.push(new int[]{c, d});

                } else {

                    // b > c : b 和 d 比较大小
                    if (b <= d) {

                        stack.pop();
                        stack.push(new int[]{a, d});

                    } else {

                        // b > d
                        // 不用管
                        continue;
                    }
                }
            }
        }

        int len = stack.size();
        int[][] arr = new int[len][2];

        for (int i = len - 1; i >= 0; i--) {
            arr[i][0] = stack.peek()[0];
            arr[i][1] = stack.pop()[1];
        }

        return arr;
    }

    // **************************************
    // 用 list 且更加简便的写法
    public int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序
        List<int[]> ans = new ArrayList<>();
        for (int[] p : intervals) {
            int m = ans.size();
            if (m > 0 && p[0] <= ans.get(m - 1)[1]) { // 可以合并
                ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]); // 更新右端点最大值
            } else { // 不相交，无法合并
                ans.add(p); // 新的合并区间
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }

    public static void main(String[] args) {
        char c = 's';
        System.out.println(c);
    }
}